package com.cty.eightdDay;

import java.util.HashMap;

/*
* 给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。
* 子数组是数组中元素的连续非空序列。
*
* */
public class Q_10 {
    public static void main(String[] args) {

    }
    //暴力枚举时间复杂度O(n^2) 空间复杂度O(1)
    public static int subarraySum(int[] nums, int k) {
        if (nums == null || nums.length == 0) return 0;
        int sum = 0,count = 0;
        // 先确定末尾的元素  从末尾遍历到开头(开头逐渐减小 子数组的长度逐渐增大)
        for (int end = 0;end < nums.length;end++) {
            sum = 0;
            // 子数组的长度每增大一次 计算一下总和 判断一下是否等于k
            for (int start = end; start >= 0;start--) {
                sum += nums[start];
                if (sum == k) {
                    count++;
                }
            }
        }
        return count;
    }


    //前缀和 + 哈希表
    public static int subarraySum2(int[] nums, int k) {
        if (nums == null || nums.length == 0) return 0;
        // 定义一个哈希表用来存储前缀和出现的次数
        HashMap<Integer, Integer> preSums = new HashMap<>();
        // 初始化前缀和和结果
        int pre = 0,count = 0;
        // 先存入0出现的次数
        preSums.put(0,1);
        for (int i = 0;i < nums.length;i++) {
            //计算前缀和
            pre += nums[i];
            // 判断哈希表中是否存在 pre - k 这个前缀和
            if(preSums.containsKey(pre - k)) {
                // 出现了 将这个前缀和出现次数加上
                count += preSums.get(pre - k);
                // 把这个前缀和出现的次数加一 注意:不能判断当前的哈希表中是否含有此时的pre
                preSums.put(pre,preSums.getOrDefault(pre,0) + 1);
            } else {
                //没有出现 说明这个前缀和的前面没有子数组相加等于k的
                preSums.put(pre,preSums.getOrDefault(pre,0) + 1);
            }
        }
        return count;
    }
}
